package com.heyqing.dynamic.NumberTower;

import java.util.Map;

/**
 * ClassName:NumberTowerSelector
 * Package:com.heyqing.dynamic.NumberTower
 * Description:
 *
 * @Date:2024/6/3
 * @Author:Heyqing
 */
public class NumberTowerSelector {
    private static int[][] maxAdd;
    private static int[][] path;
    private static int[][] d;
    private static int n;

    public NumberTowerSelector() {
        NumberTower numberTower = new NumberTower();
        n = numberTower.getNumberTowerFloor();
        d = numberTower.getNumberTower();
        maxAdd = new int[n][n];
        path = new int[n][n];
    }
    public static void findMax() {
        initBottom();
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) { // 注意：列数不超过行数
                if (j == 0) {
                    // 如果是第一列，只能向右走
                    maxAdd[i][j] = d[i][j] + maxAdd[i + 1][j + 1];
                    path[i][j] = 1;
                } else if (j == i) {
                    // 如果是最后一列，只能向左走
                    maxAdd[i][j] = d[i][j] + maxAdd[i + 1][j];
                    path[i][j] = 0;
                } else {
                    // 中间列，选择左右中较大的
                    int left = d[i][j] + maxAdd[i + 1][j];
                    int right = d[i][j] + maxAdd[i + 1][j + 1];
                    if (left > right) {
                        maxAdd[i][j] = left;
                        path[i][j] = 0;
                    } else {
                        maxAdd[i][j] = right;
                        path[i][j] = 1;
                    }
                }
            }
        }
        printResult();
    }
    private static void printResult() {
        System.out.println("最大和为: " + maxAdd[0][0]);
        // 根据path数组输出路径信息
        System.out.print("路径为: ");
        int x = 0, y = 0; // 从顶点开始
        while (x < n - 1) { // 不到最后一层就继续输出
            System.out.print("-> " + (y + 1)); // 输出列号（从1开始）
            y += path[x][y]; // 根据path数组选择向左还是向右
            x++;
        }
        System.out.println("-> " + (y + 1));
        x = 0;
        y = 0;
        System.out.print("路径对应值为: ");
        while (x < n ) {
            System.out.print("-> " + d[x][y]);
            y += path[x][y];
            x++;
        }

    }
    private static void initBottom() {
        for (int i = 0; i < n; i++) {
            maxAdd[n - 1][i] = d[n - 1][i];
            path[n - 1][i] = -1;
        }
    }

}
